import java.util.ArrayList;

/***************************************************************************
 *                                                                         *
 *                 Copyright (c) 2011, QingdaoSport.com                    *
 *                                                                         *
 *                         All Rights Reserved                             *
 *                                                                         *
 *      This is unpublished proprietary source code of QingdaoSport.       *
 *        The copyright notice above does not evidence any actual          *
 *              or intended publication of such source code.               *
 *                                                                         *
 ***************************************************************************/

/**
 * @author yongjunt
 */
public class MiniCircle {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<Point> pointList = new ArrayList<Point>();

        //pointList.add(new Point(1,0));
        pointList.add(new Point(0, 2));
        //pointList.add(new Point(0,-1));
        //pointList.add(new Point(2,1));
        //pointList.add(new Point(6,6));
        pointList.add(new Point(7, 8));
        //pointList.add(new Point(-1,-2));
        pointList.add(new Point(-1, 0));

        MiniCircleForMultiPoint multipointCircle = new MiniCircleForMultiPoint(pointList);
        try {
            Point p = multipointCircle.getCenterPoint();
            System.out.println("Center point x=" + p.getX() + ", y=" + p.getY());
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

}

class Point {
    private float x;
    private float y;

    public Point(float x, float y) {
        this.x = x;
        this.y = y;
    }

    public Point() {
        x = 0;
        y = 0;
    }

    public float getX() {
        return x;
    }

    public void setX(float x) {
        this.x = x;
    }

    public float getY() {
        return y;
    }

    public void setY(float y) {
        this.y = y;
    }

    @Override
    public boolean equals(Object p) {
        Point tmp = (Point) p;
        if (this.x == tmp.getX() && this.y == tmp.getY())
            return true;
        else
            return false;
    }
}

class MiniCircleForThreePoint {
    private Point p1;
    private Point p2;
    private Point p3;

    private Point center;
    private float radius2;

    public Point getCenter() {
        return center;
    }

    public void setCenter(Point center) {
        this.center = center;
    }

    public float getRadius2() {
        return radius2;
    }

    public void setRadius2(float radius2) {
        this.radius2 = radius2;
    }

    public MiniCircleForThreePoint(Point p1, Point p2, Point p3) {
        this.p1 = p1;
        this.p2 = p2;
        this.p3 = p3;
    }

    //for example, x1, x2, x3 is in order, and y1, y2, y3 is also in order, DESC or ASC
    private boolean isInOrder() {
        /*
		if(p3.getX()==p2.getX() && p3.getX()==p1.getX())
			return true;
		else if(p3.getX()==p2.getX() && p3.getX()!=p1.getX())
			return false;
		else if(p3.getX()==p1.getX() && p3.getX()!=p2.getX())
			return false;
		else if(p1.getX()==p2.getX() && p3.getX()!=p1.getX())
			return false;
		*/
        float tmp1 = (p3.getY() - p2.getY()) * (p3.getY() - p1.getY());
        float tmp2 = (p3.getX() - p2.getX()) * (p3.getX() - p1.getX());
        if (tmp1 * tmp2 >= 0)
            return true;
        else
            return false;
    }

    private float max(float f1, float f2, float f3) {
        float tmp = f1;
        if (f2 > tmp)
            tmp = f2;
        if (f3 > tmp)
            tmp = f3;
        return tmp;
    }

    private float min(float f1, float f2, float f3) {
        float tmp = f1;
        if (f2 < tmp)
            tmp = f2;
        if (f3 < tmp)
            tmp = f3;
        return tmp;
    }

    public Point getCenterPoint() {
        float x1 = p1.getX();
        float y1 = p1.getY();
        float x2 = p2.getX();
        float y2 = p2.getY();
        float x3 = p3.getX();
        float y3 = p3.getY();
        float x, y;

        if (isInOrder()) {
            x = (max(x1, x2, x3) + min(x1, x2, x3)) / 2;
            y = (max(y1, y2, y3) + min(y1, y2, y3)) / 2;
        } else {
            float tmp1, tmp2;
            tmp1 = (float) ((y2 - y1) * (y3 * y3 - y1 * y1 + x3 * x3 - x1 * x1) - (y3 - y1) * (y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1));
            tmp2 = (float) (2 * (x3 - x1) * (y2 - y1) - 2 * ((x2 - x1) * (y3 - y1)));
            x = (float) (tmp1 / tmp2);
            tmp1 = (float) ((x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1) - (x3 - x1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1));
            tmp2 = (float) (2 * (y3 - y1) * (x2 - x1) - 2 * ((y2 - y1) * (x3 - x1)));
            y = (float) (tmp1 / tmp2);
        }
        this.center = new Point(x, y);
        radius2 = (x - x1) * (x - x1) + (y - y1) * (y - y1);
        float tmp = (x - x2) * (x - x2) + (y - y2) * (y - y2);
        if (radius2 < tmp)
            radius2 = tmp;
        return center;
    }
}

class MiniCircleForMultiPoint {
    private ArrayList<Point> pointList = new ArrayList<Point>();

    public MiniCircleForMultiPoint(ArrayList<Point> pointList) {
        //remove the duplicated point
        for (int i = 0; i < pointList.size(); i++) {
            if (this.pointList.contains(pointList.get(i)))
                continue;
            else
                this.pointList.add(pointList.get(i));
        }
    }

    public Point getCenterPoint() throws Exception {
        int size = pointList.size();
        if (size < 3) throw new Exception("point list is less than 3!");
        for (int i = 0; i < size - 2; i++) {
            for (int j = i + 1; j < size - 1; j++) {
                for (int t = j + 1; t < size; t++) {
                    MiniCircleForThreePoint threePointCircle = new MiniCircleForThreePoint(pointList.get(i), pointList.get(j), pointList.get(t));
                    Point tmp = threePointCircle.getCenterPoint();
                    //System.out.println("tmp point x=" + tmp.getX() + ", y=" + tmp.getY());
                    //float radius = (tmp.getX()-pointList.get(i).getX())*(tmp.getX()-pointList.get(i).getX())
                    //+ (tmp.getY()-pointList.get(i).getY())*(tmp.getY()-pointList.get(i).getY());
                    if (isAllPointInCircle(tmp, threePointCircle.getRadius2(), pointList))
                        return tmp;
                }
            }
        }
        throw new Exception("Algorithm has some error, can not caculate the circle center!");
    }

    private boolean isAllPointInCircle(Point centerPoint, float radius, ArrayList<Point> pointList) {
        for (int i = 0; i < pointList.size(); i++) {
            float length = (centerPoint.getX() - pointList.get(i).getX())
                    * (centerPoint.getX() - pointList.get(i).getX())
                    + (centerPoint.getY() - pointList.get(i).getY())
                    * (centerPoint.getY() - pointList.get(i).getY());
            //System.out.println("length-radius=" + (length-radius));
            if (length > radius) {
                return false;
            }
        }
        return true;
    }
}